#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    void back_tracking(vector<vector<int>>& ans, vector<int>& nums, int pi, vector<int> perm, vector<int> vis)
    {
        if (pi >= nums.size())
        {
            ans.push_back(perm);
            return;
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            if (vis[i] == 1)
            {
                continue;
            }
            perm.push_back(nums[i]);
            vis[i] = 1;
            back_tracking(ans, nums, pi + 1, perm,vis);
            vis[i] = 0;
            perm.pop_back();
        }
        return;
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> perm;
        vector<int> vis;
        vis.resize(nums.size());
        back_tracking(ans, nums, 0, perm,vis);

        return ans;
    }
};

int main()
{
    Solution s;

    vector<int> v = { 1,2,3 };
    
    auto vv = s.permute(v);

    for (auto ee : vv)
    {
        for (auto e : ee)
        {
            cout << e << ' ';;
        }
        cout << endl;
    }
    return 0;
}